/**
 * @author 徐楠
 * @date 2022/1/23 10:50
 * @version 1.0
 */

package com.xunan.likou;

public class DeletePalindromeSubsequence {
    public static void main(String[] args) {
        String s = "bbaabaaa";
        //"bbaabaaa"先删除回文子序列bbb ,再删除“aaaaa”
        //System.out.println(s.length());
        //System.out.println(s.isEmpty());
        int result = removePalindromeSubRight(s);
        System.out.println(result);
    }

    public static int removePalindromeSubRight(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2; ++i) {
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                return 2;
            }
        }
        return 1;
    }

    public static int removePalindromeSub(String s) {

        int result = 0;
        while (!s.isEmpty()) {
            String temp = longestPalindrome1(s);
            s = s.replaceAll(temp, "");
            result++;
        }

        return result;
    }

    public static String longestPalindrome1(String s) {
        //非空判断
        if ((s == null) || s.length() == 0) {
            return null;
        }
        //将字符串转换为字符数组
        char[] oriArray = s.toCharArray();
        int first = 0;
        int end = 0;//当前字符串中回文串的始末位置 包含末位置

        for (int i = 0; i < oriArray.length - 1; i++)//两次循环 查找字符串的所有子串
        {
            for (int j = i; j < oriArray.length; j++) {
                //判断子串是否为回文串
                int left = i, right = j;//记录左侧右侧的位置
                while (left < right)//左侧下标小于右侧下标时 比较未完成
                {
                    if (oriArray[left] != oriArray[right])
                        break;//如果出现对称位置不相等元素  则不是回文串跳出循环
                    //判断下一对称位置
                    left++;
                    right--;

                }
                if (left >= right)//是否比较完成 是字符串是否为回文串的判断条件
                {
                    if (j - i > end - first)//查找到回文串 且长度大于当前存储的回文串长度
                    {
                        //替换当前回文串
                        first = i;
                        end = j;
                    }
                }
			/*if(isPlalindrome(oriArray,i,j))//是回文串
			{
				if(j-i>end-first)//查找到回文串
				{
					//替换当前回文串
					first=i;
					end=j;
				}
			}*/
            }
        }
        //查找结束  将数组转化为字符串返回
        return String.valueOf(oriArray, first, end - first + 1);
    }
}
